#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MEM(a,b) memset(a,(b),sizeof(a)) #define MAX(a,b) ((a) > (b) ? (a) : (b)) #define MIN(a,b) ((a) < (b) ? (a) : (b)) #define MP make_pair #define pb push_back #define maxn 10000 #define maxt 100 #define maxv 1000000 #define inf 1000000000 #define M 1000000007 typedef long long LL; typedef pair pi; typedef vector vi; typedef vector vs; typedef vector vd; typedef vector vpi; LL best[200005]; vi A,B; int main() { int i,j,k,n,T,m=0,cs=0; scanf("%d",&n); assert(n>=3 && n<=100000); LL cc=0; for(i=0;i=1 && w<=2 && c>=1 && c<=1000000000); m+=w; cc+=c; if(w==1) A.pb(c); else B.pb(c); } if(A.size()) sort(A.begin(),A.end()); if(B.size()) sort(B.begin(),B.end()); int a=0,b=0; int t1=A.size(),t2=B.size(); best[m]=cc; for(i=m-1;i>=1;i--) { LL cost=0; int type=-1; if(acost) cost=cc-A[a],type=0; if(b0 && cc+A[a-1]-B[b]>cost) cost=cc+A[a-1]-B[b],type=1; best[i]=cost; if(type==0) cc-=A[a],a++; if(type==1) cc+=(A[a-1]-B[b]),a--,b++; } // using only weight=2 items, from maximum to minimum cc=0; if(t2) reverse(B.begin(),B.end()); for(i=2,b=0;i<=m && b1) cout<<" "; cout<